package P4树形结构;

import java.util.LinkedList;

//二叉树
public class BinaryTree {
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
//        bt.createByLevelTraversal("12345#67##8##9");
        bt.createByParenthesizedNotationl("1(2(4(7,),5(,8)),3(6,))");
        bt.levelOrder();
        bt.preOrder();
        bt.preOrderIteration();
        bt.inOrder();
        bt.inOrderIteration();
        bt.postOrder();
        bt.postIteration();
    }

    private class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
        }
    }

    private Node root;

    //给定拓展层序遍历的结果 进行构建 "1234#5#6###7"
    public void createByLevelTraversal(String s) {
        root = createByLevelTraversal(s, 0);
    }

    private Node createByLevelTraversal(String s, int i) {
        if (s.charAt(i) == '#') {
            return null;
        } else {
            int num = Integer.parseInt(s.charAt(i) + "");
            Node node = new Node(num);
            int leftChildIndex = 2 * i + 1;
            int rightChildIndex = 2 * i + 2;
            if (leftChildIndex < s.length()) {
                node.left = createByLevelTraversal(s, leftChildIndex);
            }
            if (rightChildIndex < s.length()) {
                node.right = createByLevelTraversal(s, rightChildIndex);
            }
            return node;
        }
    }

    //给定括号表示法的结果 进行构建 "1(2(4(7,),5(,8)),3(6,))"
    public void createByParenthesizedNotationl(String s) {
        LinkedList<Node> stack = new LinkedList<>();
        int k = 1;
        Node p = null;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                k = 1;
                stack.push(p);
            } else if (c == ')') {
                stack.pop();
            } else if (c == ',') {
                k = 2;
            } else {
                p = new Node(Integer.parseInt(c + ""));
                if (root == null) {
                    root = p;
                } else {
                    if (k == 1) {
                        stack.peek().left = p;
                    } else {
                        stack.peek().right = p;
                    }
                }
            }
        }
    }

    //先序遍历
    public void preOrder() {
        StringBuilder sb = new StringBuilder("先序遍历:[");
        preOrder(root, sb);
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    private void preOrder(Node node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        sb.append(node.data);
        sb.append(',');
        sb.append(' ');
        preOrder(node.left, sb);
        preOrder(node.right, sb);
    }

    public void preOrderIteration() {
        StringBuilder sb = new StringBuilder("先序遍历-迭代:[");
        LinkedList<Node> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            sb.append(cur.data);
            sb.append(',');
            sb.append(' ');
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    //中序遍历
    public void inOrder() {
        StringBuilder sb = new StringBuilder("中序遍历:[");
        inOrder(root, sb);
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    private void inOrder(Node node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        inOrder(node.left, sb);
        sb.append(node.data);
        sb.append(',');
        sb.append(' ');
        inOrder(node.right, sb);
    }

    public void inOrderIteration() {
        StringBuilder sb = new StringBuilder("中序遍历-迭代:[");
        LinkedList<Node> stack = new LinkedList<>();
        Node p = root;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            sb.append(cur.data);
            sb.append(',');
            sb.append(' ');
            if (cur.right != null) {
                p = cur.right;
                while (p != null) {
                    stack.push(p);
                    p = p.left;
                }
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    //后序遍历
    public void postOrder() {
        StringBuilder sb = new StringBuilder("后序遍历:[");
        postOrder(root, sb);
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    private void postOrder(Node node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        postOrder(node.left, sb);
        postOrder(node.right, sb);
        sb.append(node.data);
        sb.append(',');
        sb.append(' ');
    }

    public void postIteration() {
        StringBuilder sb = new StringBuilder("后序遍历-迭代:[");
        LinkedList<Node> stack = new LinkedList<>();
        Node p = root;
        Node pre = null;
        while (!stack.isEmpty() || p != null) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            Node node = stack.pop();
            if (node.right == null || node.right == pre) {
                sb.append(node.data);
                sb.append(',');
                sb.append(' ');
                pre = node;
            } else {
                stack.push(node);
                p = node.right;
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    //层序遍历
    public void levelOrder() {
        StringBuilder sb = new StringBuilder("层序遍历:[");
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            sb.append(node.data);
            sb.append(',');
            sb.append(' ');
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }
}